package com.datastructure.test.printbinarytreeinzigzagorder;

import java.util.ArrayList;

public class PrintBinaryTreeInZigzagOrder {

    ArrayList<ArrayList<Integer>> data = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(4);
        treeNode.right.right=new TreeNode(5);
        PrintBinaryTreeInZigzagOrder printBinaryTreeInZigzagOrder = new PrintBinaryTreeInZigzagOrder();
        printBinaryTreeInZigzagOrder.Print(treeNode);
    }

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if(pRoot==null){
            return data;
        }
        levelOfPrint(pRoot,0);
        for (int i = 0; i < data.size(); i++) {
            if(i%2==1){
                ArrayList<Integer> integers = data.get(i);
                int size = integers.size();
                for (int j = 0; j < size /2; j++) {
                    int temp = integers.get(j);
                    integers.set(j,integers.get(size-j-1));
                    integers.set(size-j-1,temp);
                }
            }
        }
        return data;
    }

    private void levelOfPrint(TreeNode pRoot,int level) {
        if(level== data.size()){
            data.add(new ArrayList<>());
        }
        ArrayList<Integer> integers = data.get(level);
        integers.add(pRoot.val);
        if(pRoot.left!=null){
            levelOfPrint(pRoot.left,level+1);
        }
        if(pRoot.right!=null){
            levelOfPrint(pRoot.right,level+1);
        }
    }


}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
